package ListNodeSecond.SwordOffer;

public class DetectCycle {
    /**
     * 给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。
     * <p>
     * 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
     * <p>
     * 说明：不允许修改给定的链表。
     * <p>
     *  
     * <p>
     * 示例 1：
     * <p>
     * <p>
     * <p>
     * 输入：head = [3,2,0,-4], pos = 1
     * 输出：返回索引为 1 的链表节点
     * 解释：链表中有一个环，其尾部连接到第二个节点。
     *
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode fastListNode = head;
        ListNode slowListNode = head;
        boolean flag = false;
        while (fastListNode.next != null && fastListNode.next.next != null) {
            fastListNode = fastListNode.next.next;
            slowListNode = slowListNode.next;
            if (slowListNode == fastListNode) {
                flag = true;
                break;
            }
        }
        if (flag) {
            ListNode pre = head;
            while (pre != slowListNode) {
                pre = pre.next;
                slowListNode = slowListNode.next;
            }
            return pre;
        }else{
            return null;
        }
    }
}
